In a max-heap, the largest element is always the root. Removing it, however, requires careful steps to maintain the heap structure.

  • Step 1: Save the root
    Store the value at the root (the max value) to return later. This leaves a hole at the top of the tree.
  • Step 2: Move the last element
    To preserve the complete tree property, the very last element of the heap is moved into the vacant root position.
  • Step 3: Restore Heap Property
    This new root value will likely violate the max-heap property, requiring a "bubble down" to fix it.
101 19 100 17 3 25 1 36
Array Representation